import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: 994. 腐烂的橘子
 * <a href="https://leetcode.cn/problems/rotting-oranges/">...</a>
 * User: DELL
 * Date: 2023-10-12
 * Time: 11:16
 */
public class Solution {
    /**
     * 解题思路: (多源广度优先搜索)
     * 首先若假设其中腐烂的橘子只有一个的话,那肯定第一时间想到的就是广度优先遍历,
     * 即先将腐烂橘子的下标存入队列中,然后每一轮均将队列中所有腐烂的橘子拿出来,
     * 然后感染其上下左右四个方向的橘子,并将感染的橘子重新入队列即可.
     * 而本题一开始不止有一个腐烂的橘子,那么就需要进行多源BFS,其实也很简单,只是
     * 开始的时候遍历整个二维数组,将所有腐烂的橘子全部入队列即可,然后一轮一轮地
     * 进行遍历即可.
     * 本题有以下几点需要注意的:
     * 1. 可以制作一个简单地哈希,使得使用队列可以简单地存放腐烂橘子的下标,即
     * (i,j) -> i * col + j;
     * 2. 使用 freshNum 标记整个单元格中还剩下的新鲜橘子数,这样子最后不用重新
     * 遍历一边单元格
     * 3. 使用 res 来记录分钟数,即每次遍历一遍队列后,就相当于过了一分钟,使用 res
     * 变量来维护分钟数即可.
     * 4. 定义两个全局数组, dr 和 dc, 这样子在遍历四个方向时直接使用 for 循环即可.
     */
    private int[] dr = new int[]{-1, 0, 1, 0};
    private int[] dc = new int[]{0, 1, 0, -1};

    public int orangesRotting(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        Queue<Integer> queue = new LinkedList<>();
        int freshNum = 0;   // 记录还剩余的新鲜橘子数
        int res = 0;        // 记录整体感染的次数,即分钟数
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 2) {
                    queue.add(i * col + j);
                } else if (grid[i][j] == 1) {
                    freshNum++;
                }
            }
        }
        // 进行广度优先遍历
        while (!queue.isEmpty() && freshNum != 0) {
            res++;
            int size = queue.size();
            while (size-- != 0) {
                int num = queue.poll();
                int r = num / col;
                int c = num % col;
                for (int i = 0; i < 4; i++) {
                    int nr = r + dr[i];
                    int nc = c + dc[i];
                    if (0 <= nr && nr < row && 0 <= nc && nc < col && grid[nr][nc] == 1) {
                        freshNum--;
                        grid[nr][nc] = 2;
                        int temp = nr * col + nc;
                        queue.add(temp);
                    }
                }
            }
        }
        return freshNum == 0 ? res : -1;
    }
}